home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group00a.txt / 000013_icon-group-sender _Thu Jan 20 17:03:40 2000.msg < prev    next >
Internet Message Format  |  2001-01-03  |  2KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id RAA23617
  4.     for icon-group-addresses; Thu, 20 Jan 2000 17:02:03 -0700 (MST)
  5. Message-Id: <200001210002.RAA23617@baskerville.CS.Arizona.EDU>
  6. Date: Thu, 20 Jan 2000 12:02:05 -0800 (PST)
  7. From: Shamim Mohamed <soar@drones.com>
  8. To: icon-group@optima.CS.Arizona.EDU
  9. Subject: Re: all permutations
  10. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  11. Status: RO
  12.  
  13.  > I need a program which generates all combinations (or permutations?)
  14.  > of 12345, i.e. 12345, 12354, 12435, etc
  15.  
  16. I wrote a program to do this some time ago. It actually writes out the
  17. permutations lexicographically, and is non-recursive. I don't remember
  18. everything about it, so if something seems strange, I might not be able
  19. to explain it!
  20.  
  21. -s
  22.  
  23.  
  24.  
  25. # procedure to find the next (lexicographically) permutation of a string
  26.  
  27. # Algorithm : to generate one string from the previous,
  28. #  i)  scan left from the end of the string till you find a char smaller
  29. #      than the one to its right;
  30. # ii)  find the smallest letter in the substring to its right; interchange
  31. #      them;
  32. # iii) sort the substring on the right
  33. # and repeat.
  34. #       This is a permutation since letters are only interchanged. This is
  35. # the next higher one by inspection. (Very long and careful inspection!)
  36.  
  37. procedure next_perm(s)
  38.  
  39.    i := *s - 1
  40.  
  41.    while i > 0 & ord(s[i]) >= ord(s[i+1]) do
  42.       i -:= 1
  43.    if i = 0 then fail
  44.  
  45.    j := i
  46.    min := i + 1
  47.    while j <= *s do {
  48.       if ord(s[j]) > ord(s[i]) & ord(s[j]) < ord(s[min]) then
  49.          min := j
  50.       j +:= 1
  51.    }
  52.    s[min] :=: s[i]
  53.    s[i+1:0] := ssort(s[i+1:0])
  54.  
  55.    return s
  56. end
  57.  
  58.  
  59. procedure main(args)
  60.  
  61.    s := args[1] | "abcde"
  62.  
  63.    write(i:=1, " ", s)
  64.    while s := next_perm(s) do
  65.       write(i+:=1, " ", s)
  66.  
  67. end
  68.  
  69. procedure ssort(s)
  70.  
  71. # The straightforward approach doesn't work if the string contains duplicates
  72.    return string(cset(s))
  73.  
  74.    ret := ""
  75.    T := table(0)
  76.  
  77.    every c := !s do T[c] +:= 1
  78.    every c := !cset(s) do
  79.       ret ||:= repl(c, T[c])
  80.    return ret
  81. end
  82.  
  83.